package ljl.codetop300;

/**
 * 这种题我说实话是最简单的，写起来就跟回家一样
 */
public class _79_search_words {

  static class test {
    char[][] board;
    String word;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
      this.board = board;
      this.word = word;
      int m = board.length;
      int n = board[0].length;
      visited = new boolean[m][n];
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
          if (board[i][j] == word.charAt(0) && search(i, j, 0)) {
            return true;
          }
        }
      }
      return false;
    }

    boolean search(int i, int j, int idx) {
      if (idx == word.length()) return true;
      if (i >= board.length || i < 0
          || j >= board[0].length || j < 0
          || visited[i][j] || board[i][j] != word.charAt(idx))
        return false;
      visited[i][j] = true;
      boolean res = search(i + 1, j, idx + 1)
          || search(i - 1, j, idx + 1)
          || search(i, j + 1, idx + 1)
          || search(i, j - 1, idx + 1);
      visited[i][j] = false;
      return res;
    }
  }

  class off {
    public boolean exist(char[][] board, String word) {
      int h = board.length, w = board[0].length;
      boolean[][] visited = new boolean[h][w];
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          boolean flag = check(board, visited, i, j, word, 0);
          if (flag) {
            return true;
          }
        }
      }
      return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
      if (board[i][j] != s.charAt(k)) {
        return false;
      } else if (k == s.length() - 1) {
        return true;
      }
      visited[i][j] = true;
      int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
      boolean result = false;
      for (int[] dir : directions) {
        int newi = i + dir[0], newj = j + dir[1];
        if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
          if (!visited[newi][newj]) {
            boolean flag = check(board, visited, newi, newj, s, k + 1);
            if (flag) {
              result = true;
              break;
            }
          }
        }
      }
      visited[i][j] = false;
      return result;
    }
  }
}
